Exercise 8 (Homework 5).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages),
computable functions)
Characterizations of \mathbf{R} and \mathbf{RE}
Let S be an infinite language.
- S\in \mathbf{RE} if and only if there exists an injective total computable function f such that \mathrm{Im}(f)=S.
- S\in \mathbf{R} if and only if there exists an injective total computable function f that is monotone increasing and such that \mathrm{Im}(f)=S.
- S\in \mathbb{R} if and only if the indicator function of S, \chi_S, is computable.
Note
Recall that, given a function f, \mathrm{Im}(f) is the image of f, that is, \mathrm{Im}(f)=\{y \mid \exists x\ y=f(x)\}. The indicator function of a set S is the Boolean valued function \chi_S s.t. \chi_S(x)=1 if and only if x\in S.